1. Field of the Invention
This invention pertains to the architecture of digital multipliers for use in high speed digital signal processing systems, and in particular to such an architecture which is optimized for implementation in very large scale integrated circuits.
2. Description of the Prior Art
Multipliers are very important building blocks of many digital systems. They are extensively used in array processors, video processors, radar signal processors, FFT processors, general digital signal processors, microcomputer/minicomputer accelerators and many other similar applications.
In the majority of applications, it is the throughput speed not the total latency in time that is the important measure of the multiplication speed. In other words, for most applications pipelined multipliers seem very attractive because of their high throughput. The conventional shift-and-add multiplier algorithm lends itself to pipelining very easily at various levels, but is requires N-1 shift-and-adds if there are N bits in the multiplicand. An alternative is using Booth's Algorithm for multiplication. This is an efficient implementation, but is difficult to pipeline and hence has a lower throughput rate than the shift-and-add algorithm.
The present application discloses a modification of the shift-and-add algorithm which achieves the same throughput rate as the original algorithm while requiring only half the number of (or even less) shift-and-add operations. Also, in many applications it is desired to use the multiplier as an unsigned magnitude multiplier to achieve an extra bit of precision, rather than a two's compliment signed multiplier. This application discloses a provision in its architecture such that the multiplier can perform both two's compliment and unsigned magnitude as well as mixed mode multiplication.